//
// Created by 子夜求知 on 2022/8/14.
//

#ifndef TREEPROJECT_TREE_H
#define TREEPROJECT_TREE_H

#include "stdio.h"
#include "stdlib.h"
#include <stdbool.h>
#include "Stack.h"
#include "Queue.h"

/**
 * 访问节点函数
 * @param biTNode
 */
void visit(BiTNode biTNode){
    printf("%d ",biTNode.data);
}

/**
 * 先序遍历二叉树算法
 * @param T
 */
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(*T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

/**
 * 中序遍历二叉树
 * @param T
 */
void InOrder(BiTree T){
    if(T!=NULL){
        PreOrder(T->lchild);
        visit(*T);
        PreOrder(T->rchild);
    }
}

/**
 * 后序遍历二叉树
 * @param T
 */
void PostOrder(BiTree T){
    if(T!=NULL){
        PreOrder(T->lchild);
        PreOrder(T->rchild);
        visit(*T);
    }
}

/**
 * 二叉树中序遍历非递归算法:
 *  一直向左走并将走过的节点入栈，直到走不下去，栈顶元素出栈，检查弹出的元素是否有右节点，如果有则将右节点存入栈中，没有则不处理
 * @param T
 */
void InOrder2(BiTree T){
    // 创建并且初始化栈
    SqStack *S =(SqStack *) malloc(sizeof (SqStack));
    InitStack(S);
    BiTree p = T;   // p是遍历指针
    while (p||!StackEmpty(*S)){  // 栈不空或p不空时循环
        if(p){
            Push(S,*p);     // 当前节点入栈
            p = p->lchild;  // 左孩子不空，一直向左走
        } else{  // 出栈并转向出栈节点的右子树
            // 栈顶元素出栈，访问出栈节点
            Pop(S,p);
            visit(*p);
            // 向右子树走，p赋值为当前节点的右孩子
            p = p->rchild;
        }   // 返回while循环继续进行if和else语句

    }
}

/**
 * 二叉树先序遍历非递归算法：
 *和中序遍历非递归算法思想类似，只需把访问节点操作放在入栈操作的前面
 * @param T
 */
void PreOrder2(BiTree T){
    // 创建并且初始化栈
    SqStack *S =(SqStack *) malloc(sizeof (SqStack));
    InitStack(S);
    BiTree p = T;   // p是遍历指针
    while (p||!StackEmpty(*S)){
        if(p){  // 一路向左
            // 访问当前节点并且入栈
            visit(*p);
            Push(S,*p);
            p = p->lchild;  // 左孩子不空，一直向左走
        } else{     // 出栈，并转向出栈节点的右子树
            Pop(S,p);   // 栈顶元素出栈
            p = p->rchild;  // 向右子树走，p赋值为当前节点的右孩子
        }   // 返回while循环继续进入if-else语句
    }
}
/**
 * 二叉树后续遍历非递归算法
 * @param T
 */
void PostOrder2(BiTree T){
    //创建并初始化栈
    SqStack *S = (SqStack *) malloc(sizeof (SqStack));
    InitStack(S);
    BiTNode *p = T;  // p:遍历指针
    BiTNode *r;      // r:记录最近访问的节点
    while (!StackEmpty(*S)||p){ // 栈空的时候或者p为空的时候推出循环
        if(p){       // 如果遍历节点p不为空，则一路向左
            p = p->lchild;
            Push(S,*p);
        } else{                           // 如果p为空的,则向右
            GetTop(*S,p);                 // 获取栈顶元素，并将栈顶元素赋值给p
            if(p->rchild&&p->rchild!=r)   // 如果p的右孩字不为空，并且右孩字未被访问过
                p = p->rchild;            // 转向右
            else{
                Pop(S, p);                // 将结点弹出
                visit(*p);                // 访问节点
                r = p;                    // 记录最近访问过的节点
                p = NULL;                 // 节点访问完之后，重置p
            }
        }
    }
}

/**
 * 层序遍历算法
 * @param T
 */
void LevelOrder(BiTree T){
    // 创建并且初始化辅助队列
    SqQueue *Q = malloc(sizeof (SqQueue));
    InitQueue(Q);
    EnQueue(Q,*T);  // 将根节点入队
    BiTree  p;  // 遍历节点
    while (!isEmpty(*Q)){   // 队列不空则循环
        DeQueue(Q,p);       // 队头节点出队
        visit(*p);          // 访问出队节点
        if(p->lchild!=NULL){
            EnQueue(Q,*(p->lchild)); // 左子树不空，则左子树根节点入队
        }
        if(p->rchild!=NULL){
            EnQueue(Q,*(p->rchild)); // 右子树不为空，则右子树根节点入队
        }
    }
}

/**
 * 通过中序遍历对二叉树线索化的递归算法
 * @param p
 * @param pre
 */
void InThread(ThreadTree p,ThreadTree pre){
    if(p!=NULL){
        InThread(p->lchild,pre);    // 递归线索化左子树
        if(p->lchild==NULL){        // 左子树为空，建立前驱线索
            p->lchild = pre;        // 让p的左指针指向指向前驱
            p->ltag = 1;
        }
        if(pre!=NULL&&pre->rchild==NULL){
            pre->rchild = p;    // 建立前驱节点的后继线索
            pre->rtag = 1;
        }
        pre = p;  // 标记当前节点成为刚刚访问过的节点
        InThread(p->rchild,pre);    // 递归线索化右子树
    }
}

/**
 * 中序遍历建立中序线索二叉树
 * @param T
 */
void CreateInThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T!=NULL){
        InThread(T,pre);    // 非空二叉树、线索化
        pre->rchild = NULL; // 线索化二叉树
        pre->rtag = 1;      // 处理遍历的最后一个节点
    }
}

void visitThread(ThreadNode threadNode){
    printf("%d ",threadNode.data);
}

/**
 * 求中序线索二叉树中中序序列下的第一个节点
 * @param p
 * @return
 */
ThreadNode *FirstNode(ThreadNode *p){
    while (p->ltag==0)
        p = p->lchild;  // 最左下节点(不一定是叶结点)
    return p;
}

/**
 * 求中序线索二叉树中节点p在中序序列下的后继
 * @param p
 * @return
 */
ThreadNode *NextNode(ThreadNode *p){
    if(p->rtag==0)
        return FirstNode(p);
    else    // rtag=1则直接返回后继节点
        return p->rchild;
}

/**
 * 利用以上两个算法，写出不含头节点的中序线索二叉树的中序遍历算法
 * @param T
 */
void Inorder(ThreadNode *T){
    ThreadNode *p = (ThreadNode *) malloc(sizeof (ThreadNode));
    for ( p= FirstNode(T); p!=NULL  ; p = NextNode(p)) {
        visitThread(*p);
    }
}
/**
 * 非递归算法求解二叉树的高度
 * @param T
 * @return
 */
int Btdepth(BiTree T){
    if(T)   // 如果树为空则返回高度为0
        return 0;
    BiTNode* Q[MaxSize];     // 创建数据类型为二叉树结点BiTNode的数组作为队列
    int front = -1,rear = -1;    // 队列的队头和队尾指针
    int level = 0,last = 0;       // level：记录二叉树高度 last：记录每一层最右边的节点
    Q[++rear] = T;          // 树的根节点入队
    while (front<rear){    // 队列不为空则进行循环
        BiTNode *p = Q[++front];    // 队头指针+1，表示队头元素出队
        if(p->lchild){
            Q[++rear] = p->lchild;  // p的左孩子入队
        }
        if(p->rchild){
            Q[++rear] = p->rchild;  // p的右孩子入队
        }
        if(front==last){            // front等于last说明该层已经遍历完
            level++;                // level自增记录层数
            last = rear;            // last指向下一层最右边的元素下标
        }
    }
    return level;
}

/**
 * 递归算法求解二叉树的高度
 * @param T
 * @return
 */
int Btdepth2(BiTree T){
    if(T)
        return 0;
    int ldep = Btdepth2(T->lchild);
    int rdep = Btdepth2(T->rchild);
    if(rdep>ldep)
        return rdep + 1;
    else
        return ldep + 1 ;
}

/**
 * 根据先序遍历序列A,中序遍历序列B，建立二叉树的二叉链表
 * @param A：先序遍历序列
 * @param B：中序遍历序列
 * @param l1：先序的第一个结点下标,初始值为1
 * @param h1：先序的最后一个结点下标，初始值为n
 * @param l2：中序的第一个结点下标,初始值为1
 * @param h2：先序的最后一个结点下标，初始值为n
 * @return
 */
BiTree PreInCreate(char A[],char B[],int l1,int h1,int l2,int h2){
    // 先序序列的第一个结点为根节点
    BiTNode *root = ( BiTNode *)malloc(sizeof (BiTree));
    root->data = A[l1];
    // 在中序序列中寻找根节点
    int i;
    for ( i = l1; B[i]!= root->data; ++i);
    int Llen = i-l2;
    int Rlen = h2-i;
    if(Llen)
        root->lchild = PreInCreate(A,B,l1+1,l1+Llen,l2,i-1);
    else
        root->lchild = NULL;
    if(Rlen)
        root->rchild = PreInCreate(A,B,h1-Rlen+1,h1,i+1,h2);
    else
        root->rchild = NULL;
    return root;
}

/**
 * 获取结点x的双亲结点
 * @param T
 * @param x
 */
BiTNode getParent(BiTree T,BiTNode x){
    if(T){
        if((T->lchild) && (T->lchild->data==x.data)){
            return *T;
        }
        if((T->rchild) && (T->rchild->data==x.data)){
            return *T;
        }
        else{
            getParent(T->lchild,x);
            getParent(T->rchild,x);
        }
    }
}

/**
 * 二叉排序树插入操作的算法
 */
 int BST_Insert(BiTree T,int k){
     if(T){     // 原树为空，新插入的记录为根节点
         T = (BiTree) malloc(sizeof (BiTNode));
         T->data = k;
         T->lchild = 0;
         T->rchild = 0;
         return 1;     // 返回1，插入成功
     }
     else if(k==T->data)  // 树中存在相同关键字的结点，插入失败
         return 0;
     else if(k<T->data)     // 插入到T的左子树
         return BST_Insert(T->lchild,k);
     else                   // 插入到T的右子树
         return BST_Insert(T->rchild,k);
 }

 /**
  * 构造二叉排序树
  * @param T
  * @param array
  * @param n
  */
 void Creat_BST(BiTree T,int array[],int n){
     T = NULL;      // 初始时T为空树
     int i = 0;
     while (i<n){   // 依次将每个关键字插入到二叉排序树中
         BST_Insert(T,array[i]);
         i++;
     }
 }

 /**
  * 二叉排序树的非递归查找算法
  * @param T
  * @param key
  * @return
  */
 BiTNode* BST_Search(BiTree T,int key){
     while (T!=NULL && key!=T->data){   // 若树空或等于根节点值，则结束循环
         if(key<T->data)    // 小于，则在左子树上查找
             T = T->lchild;
         else       // 大于，则在左右子树上查找
             T = T->rchild;
     }
     return T;
 }


 /**
  * 交换二叉树中所有结点左右子树
  * @param bt
  */
 void swapbitree(BiTree bt){
     BiTree p;
     if(bt==0)
         return;
     swapbitree(bt->lchild);
     swapbitree(bt->rchild);
     p = bt->lchild;
     bt->lchild = bt->rchild;
     bt->rchild = p;
 }

 /**
  * 判断两个二叉树是否相同的算法
  * @param bt1
  * @param bt2
  * @return
  */
 int judgeBiTree(BiTree bt1,BiTree bt2){
     if(bt1==0&&bt2==0)
         return 1;
     else if(bt1=0|| bt2==0 || bt1->data!=bt2->data)
         return 0;
     else
         return judgeBiTree(bt1->lchild,bt2->lchild)*judgeBiTree(bt1->rchild,bt2->rchild);
 }

 /**
  * 判断二叉树是否为二叉排序树
  */
int minnum=-32768,flag=1;
void inorder(BiTree bt)
{
    if (bt!=0)
    {
        inorder(bt->lchild);
        if(minnum>bt->data)
            flag=0;
        minnum=bt->data;
        inorder(bt->rchild);
    }
}

//用于记录层次，这个lev变量一定要放到函数外面，因为该算法使用了递归
int lev=0;
/**
 * 设计求结点在二叉排序树中层次的算法
 * @param bt
 * @param x
 */
void level(BiTree bt,int x)
{
    if(bt!=NULL){
        lev++;
        if(bt->data==x)
            return;
        else if(bt->data>x)
            level(bt->lchild,x);
        else
            level(bt->rchild,x);
    }
}

/**
 * 统计二叉树中结点个数
 * @param bt
 * @param count
 */
void countnode(BiTree bt,int *count){
    if(bt!=0){
        count++;
        countnode(bt->lchild,count);
        countnode(bt->rchild,count);
    }
}

/**
 * 设计计算二叉树种所有节点之和的算法
 * @param bt
 * @param s
 */
void sum(BiTree bt,int *s){
    if(bt!=0){
        s = s + bt->data;
        sum(bt->rchild,s);
        sum(bt->rchild,s);
    }
}
#endif //TREEPROJECT_TREE_H
